//https://www.bilibili.com/video/BV1d54y1f7B3?spm_id_from=333.788.videopod.episodes&vd_source=d6fe65f095f01f05591e89d810720ccc&p=20
// 2024-10-21

import java.util.Arrays;

public class P026_省份数量_深度优先 {

    public static void main(String[] args) {
        System.out.println(fun(new int[][] {{1,1,0},{1,1,0},{0,0,1}}));
//        System.out.println(fun(new int[][] {5,5,5,20}));
    }

    private static int fun(int[][] citysConnexted) {
        int citys = citysConnexted.length;
        boolean[] visited = new boolean[citys];
        int provinces = 0;//计数器
        for (int i = 0; i < citys; i++) {
            if (!visited[i]) {//未被访问
                // 深度优先 时间复杂度o(n*n)
                dfs(i,citys,visited,citysConnexted);
                provinces++;    //省份++
            }
        }
        return provinces;
    }

    private static void dfs(int i, int citys, boolean[] visited, int[][] citysConnexted) {
        for (int j = 0; j < citys; j++) {
            if (citysConnexted[i][j] == 1 && !visited[j]) {//未打标时候才需要判断
                visited[j] = true;  //i与j相连
                dfs(j,citys,visited,citysConnexted);//递归与j相连的元素
            }
        }
    }
}
